package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC467 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 链接：https://leetcode-cn.com/problems/unique-substrings-in-wraparound-string/solution/dong-tai-gui-hua-java-by-zyxwmj-dn12/
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 有意识的题目，一开始我就相差了，想复杂了！
     * @return:
     */
    class Solution {
        public int findSubstringInWraproundString(String p) {
            // 记录 p 中以每个字符结尾的最长连续子串的长度
            int[] dp = new int[26];
            char[] array = p.toCharArray();
            // 记录当前连续子串的长度
            int count = 0;
            // 遍历 p 中的所有字符
            for (int i = 0; i < array.length; i++) {
                // 判断字符是否连续
                if (i > 0 && (array[i] - array[i - 1] - 1) % 26 == 0) {
                    // 连续则自加
                    count++;
                } else {
                    // 不连续则刷新
                    count = 1;
                }
                // 只存储最长的连续长度
                dp[array[i] - 'a'] = Math.max(dp[array[i] - 'a'], count);
            }
            int result = 0;
            // 统计所有以每个字符结尾的最长连续子串的长度，就是唯一相等子串的个数
            for (int i : dp) {
                result += i;
            }
            return result;
        }
    }


    class Solution_Fail_And_Need_Further_fix {
        public int findSubstringInWraproundString(String p) {
            if (null == p || p.length() <= 0) return 0;
            StringBuilder noRepeat = new StringBuilder();
            char lastc = 0;
            for (int i = 0; i < p.length(); i++) {
                if (p.charAt(i) == lastc) continue;
                noRepeat.append(p.charAt(i));
                lastc = p.charAt(i);
            }
            p = noRepeat.toString();

            int left = 0, right = 0, count = 0;
            char lastChar = 0;
            boolean[] occupy = new boolean[26];
            while (right < p.length()) {
                char cur = p.charAt(right);
                if (!(lastChar == 0 || cur == lastChar + 1 || ('z' == lastChar && cur == 'a'))) {
                    // need to shrunk window.
                    int curWindowAdd = notOccupyLength(occupy, p, left, right - 1);
                    count += curWindowAdd;
                    left = right;
                }

                ++right;
                lastChar = cur;
            }

            if (left <= p.length() - 1) {
                int curWindowAdd = notOccupyLength(occupy, p, left, p.length() - 1);
                count += curWindowAdd;
            }

            return count;
        }

        public int notOccupyLength(boolean[] occupy, String p, int start, int end) {
            int curStart = start, curEnd = start, partCount = 0;
            while (curEnd <= end) {
                while (curStart <= end && occupy[p.charAt(curStart) - 'a']) ++curStart;
                curEnd = curStart;
                while (curEnd <= end && !occupy[p.charAt(curEnd) - 'a']) {
                    occupy[p.charAt(curEnd) - 'a'] = true;
                    ++curEnd;
                }
                partCount += (curEnd - curStart) * (curEnd - curStart + 1) / 2;
                curStart = curEnd;
            }

            if (curEnd > curStart) partCount += (curEnd - curStart) * (curEnd - curStart + 1) / 2;
            return partCount;
        }
    }

    public void run() {
        Solution solution = new Solution();
        String p = "zabcdhijkefghi";
        boolean[] occupy = new boolean[26];
//        System.out.println(solution.notOccupyLength(occupy, p, 0, 8));
//        System.out.println(solution.notOccupyLength(occupy, p, 9, 13));
        System.out.println(solution.findSubstringInWraproundString("aabb"));
    }

    public static void main(String[] args) throws Exception {
        LC467 an = new LC467();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
